package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 226. 翻转二叉树
 * 二叉树的中序遍历
 * 只要能遍历二叉树的所有节点都可以轻松完成，
 * 我们还可以使用二叉树的中序遍历来解决
 *
 * 其他遍历也可以
 *
 * @author fy
 * @date 2022-04-17 16:35
 */
public class Solution226_5 {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();

            TreeNode left = node.left;
            node.left = node.right;
            node.right = left;

            // 这里因为翻转了的原因, 不再是right了
            node = node.left;
        }
        return root;
    }

}
